%0 Conference Proceedings
%4 sid.inpe.br/sibgrapi/2016/07.22.18.26
%2 sid.inpe.br/sibgrapi/2016/07.22.18.26.36
%@doi 10.1109/SIBGRAPI.2016.016
%T Convex Hull for Probabilistic Points
%D 2016
%A Atalay, F. Betul,
%A Friedler, Sorelle,
%A Xu, Dianna,
%@affiliation TOBB University of Economics and Technology
%@affiliation Haverford College
%@affiliation Bryn Mawr College
%E Aliaga, Daniel G.,
%E Davis, Larry S.,
%E Farias, Ricardo C.,
%E Fernandes, Leandro A. F.,
%E Gibson, Stuart J.,
%E Giraldi, Gilson A.,
%E Gois, João Paulo,
%E Maciel, Anderson,
%E Menotti, David,
%E Miranda, Paulo A. V.,
%E Musse, Soraia,
%E Namikawa, Laercio,
%E Pamplona, Mauricio,
%E Papa, João Paulo,
%E Santos, Jefersson dos,
%E Schwartz, William Robson,
%E Thomaz, Carlos E.,
%B Conference on Graphics, Patterns and Images, 29 (SIBGRAPI)
%C São José dos Campos, SP, Brazil
%8 4-7 Oct. 2016
%I IEEE Computer Society´s Conference Publishing Services
%J Los Alamitos
%S Proceedings
%K probabilistic, approximate, convex hull.
%X We analyze the correctness of an O(n log n) time divide-and-conquer algorithm for the convex hull problem when each input point is a location determined by a normal distribution. We show that the algorithm finds the convex hull of such probabilistic points to precision within some expected correctness determined by a user-given confidence value phi. In order to precisely explain how correct the resulting structure is, we introduce a new certificate error model for calculating and understanding approximate geometric error based on the fundamental properties of a geometric structure. We show that this new error model implies correctness under a robust statistical error model, in which each point lies within the hull with probability at least phi, for the convex hull problem.
%@language en
%3 grapi.pdf